package org.atlantis.juc.lock;

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.LockSupport;

public final class ReentryLock implements Lock {

	// state表示加锁的次数，如果state=0则表示当前锁是空闲的
	private AtomicInteger state = new AtomicInteger();
	private volatile Thread exclusiveOwnerThread;
	private AtomicReference<Node> tail = new AtomicReference<Node>();
	private AtomicReference<Node> head = new AtomicReference<Node>();

	@Override
	public void lock() {
		// 非公平锁，首先判断--如果当前锁是空闲的，则直接获取锁，不用管CLH队列里等待获取锁的线程
		if (state.compareAndSet(0, 1)) exclusiveOwnerThread = Thread.currentThread();
		else acquire();
	}

	private void acquire() {
		// 再一次尝试获取锁，能获取就直接获取，不能获取就只能加入等待队列
		if (!tryAcquire() && blockNode(addWaiter())) Thread.currentThread().interrupt();
	}

	// 尝试获取锁
	private boolean tryAcquire() {
		Thread currentThread = Thread.currentThread();
		if (state.compareAndSet(0, 1)) exclusiveOwnerThread = currentThread;
		// 如果当前线程已经获得锁，那么再次加锁时就将加锁次数+1
		else if (currentThread == exclusiveOwnerThread) state.incrementAndGet();
		else return false;
		return true;
	}

	// 将当前无法获取锁的线程封装成一个Node对象，并加入CLH队尾，然后返回
	private Node addWaiter() {
		Node node = new Node(Thread.currentThread());
		Node tailNode = tail.get();
		// 如果当前的tail节点存在（tail != null），则采用CAS的方式将Node加入到队尾
		if (tailNode != null) {
			node.prev = tailNode;
			if (tail.compareAndSet(tailNode, node)) {
				tailNode.prev = node;
				return node;
			}
		}
		enq(node);
		return node;
	}

	// 将新Node加入到CLH队列尾
	private Node enq(Node node) {
		while (true) {
			Node tailNode = tail.get();
			if (tailNode == null) { // 如果tailNode=null则表示CLH队列为空
				Node headNode = new Node(); // 初始化头节点（头节点只是一个虚拟节点，没有实际作用）
				headNode.next = node;
				node.prev = headNode;
				if (head.compareAndSet(null, headNode)) {
					// 将当前的节点设置为尾节点：HeadNode(dummy) -> TailNode(current node)
					tail.set(node);
					return headNode;
				}
			} else {
				node.prev = tailNode;
				// 如果tailNode!=null则表示CLH队列不为空，则将node设置为尾节点（如果不成功则一直设置，直到成功）
				if (tail.compareAndSet(tailNode, node)) {
					tailNode.next = node;
					return tailNode;
				}
			}
		}
	}

	// 将已添加到CLH队列尾的Node进行阻塞，阻塞前再进行一次tryAcquire尝试，如果成功则直接返回
	private boolean blockNode(Node node) {
		try {
			boolean interrupted = false;
			while (true) {
				Node prevNode = node.getPrevNode();
				/*
				 * prevNode == head.get()表示当前node是CLH队列中第一个节点，只有prevNode ==
				 * head.get() && tryAcquire()为true时才会终止循环返回，否则就会永远循环等待
				 */
				if (prevNode == head.get() && tryAcquire()) {
					setHead(node);
					prevNode.next = null; // help GC
					return interrupted;
				}
				if (shouldParkAfterFailedAcquire(prevNode, node) && parkAndCheckInterrupt()) interrupted = true;
			}
		} catch (RuntimeException e) {
			cancelAcquire(node);
			throw e;
		}
	}

	// 取消获取锁
	private void cancelAcquire(Node node) {
		if (node == null) return;
		node.thread = null;
		Node prev = node.prev;
		while (prev.waitStatus.get() == Node.CANCELLED)
			node.prev = prev = prev.prev;
		node.waitStatus.set(Node.CANCELLED);
		if (node == tail.get() && tail.compareAndSet(node, prev)) {
			prev.next = null;
		} else {
			int ws = 0;
			if (prev != head.get()
					&& ((ws = prev.waitStatus.get()) == Node.SIGNAL || (ws == Node.CANCELLED && prev.waitStatus.compareAndSet(
							ws, Node.SIGNAL))) && prev.thread != null) {
				Node nextNode = node.next;
				if (nextNode != null && nextNode.waitStatus.get() == Node.SIGNAL) prev.next = nextNode;
			} else {
				unparkSuccessor(node);
			}
			node.next = node;
		}
	}

	// 将一个节点设置为头节点，因为头节点是虚拟节点所以thread是null
	private void setHead(Node node) {
		node.thread = null;
		node.prev = null;
		head.set(node);
	}

	/*
	 * 检查node的状态，看是否要对它进行阻塞，如果当前node是cancel状态则没必要阻塞。 检查规则：
	 * 1.如果前继节点状态为SIGNAL，则表示当前节点需要unpark，则返回true
	 * 2.如果前继节点状态为CANCEL，则表示前继节点需要被剔除，则回溯到一个非CANCEL的前继节点，返回false
	 * 3.如果前继节点状态为非SIGNAL，非CANCEL，则设置前继的状态为SIGNAL，返回false
	 */
	private boolean shouldParkAfterFailedAcquire(Node prev, Node node) {
		int ps = prev.waitStatus.get();
		if (ps == Node.SIGNAL) return true;
		if (ps == Node.CANCELLED) {
			do {
				// 剔除状态为Cancel的线程节点
				node.prev = prev = prev.prev;
			} while (prev.waitStatus.get() == Node.CANCELLED);
			prev.next = node;
		} else {
			prev.waitStatus.compareAndSet(ps, Node.SIGNAL);
		}
		return false;
	}

	// 挂起线程
	private boolean parkAndCheckInterrupt() {
		LockSupport.park(this);
		return Thread.interrupted();
	}

	@Override
	public void unlock() {
		release();
	}

	private boolean release() {
		if (tryRelease()) {
			Node h = head.get();
			if (h != null && h.waitStatus.get() != 0) unparkSuccessor(h);
			return true;
		}
		return false;
	}

	private boolean tryRelease() {
		int c = state.get() - 1;
		if (Thread.currentThread() != exclusiveOwnerThread) throw new IllegalMonitorStateException();
		boolean free = false;
		if (c == 0) {
			free = true;
			exclusiveOwnerThread = null;
		}
		state.set(c);
		return free;
	}

	/*
	 * 找出第一个可以unpark的线程
	 */
	private void unparkSuccessor(Node node) {
		int ws = node.waitStatus.get();
		if (ws == Node.SIGNAL) node.waitStatus.compareAndSet(ws, 0);
		Node nextNode = node.next;
		if (nextNode == null || nextNode.waitStatus.get() > 0) {
			nextNode = null;
			for (Node n = tail.get(); n != null && n != node; n = n.prev) {
				if (n.waitStatus.get() == Node.CANCELLED) nextNode = n;
			}
		}
		LockSupport.unpark(nextNode.thread);
	}

	static final class Node {

		// 因为超时或中断，该线程已经被取消，需要从CLH队列中剔除
		static final int CANCELLED = 1;
		// 线程的后继线程已经（或将要）被阻塞，当当前线程release或cancel时要释放后继线程（unpark）
		static final int SIGNAL = -1;

		volatile Node next;
		volatile Node prev;
		volatile Thread thread;
		// 等待状态默认为0,0表示无状态
		volatile AtomicInteger waitStatus = new AtomicInteger();

		Node() {
		}

		Node(Thread thread) {
			this.thread = thread;
		}

		Node getPrevNode() {
			if (prev == null) throw new NullPointerException();
			return prev;
		}
	}
}
